1. Field of the Invention
The invention relates to sensing and display devices and, in particular, to devices which locate and sense or display multi-dimensional signal energy at different detected levels of refinement.
2. Description of the Prior Art
Display devices such as video monitors or LCD arrays process electrical input signals which then modulate a source of visible light for display. Similarly, video cameras receive modulated visible light signals which are converted to electrical signals for transmission or storage. They are special cases of sensor type and display type transducers and associated electronics which accept an input signal and convert it to an appropriate form for further processing.
Multi-dimensional signal energy which is typically directly received by such sensors to be displayed by such displays, is distributed both in spatial location and in spatial frequency. Conventional systems for processing such multi-dimensional signals typically apply transforms of the mathematical space of multi-dimensional signals in order to isolate and measure spatial and frequency characteristics of the signal. For example, considering two-dimensional signals received by a video camera to be analyzed as to content, i.e. subjected to pattern recognition, a transform of the signal can produce information as to the existence and location of sharp edges, which may help identify the outline of an object being sought.
Multi-dimensional signals are typically represented by a multi-dimensional array of data. For a two-dimensional array, which may represent an image, a transform of the array is normally a two-dimensional transform which is computed as a sequence of two one-dimensional transforms applied to the rows and columns of the two dimensional array of data. The basis functions for a two-dimensional transform, that is, the orthogonal set of functions which when multiplied by the respective transform coefficients and summed produce the original two-dimensional signal, are known to be "product transforms" calculated as the products of the basis functions for the corresponding one-dimensional transforms.
The use of such two-dimensional transforms in the context of pattern recognition has two disadvantages. Firstly, the number of calculational steps is high and therefore the time required long. Secondly, the basis functions do not "localize" signal energy, that is, associate a particular spatial frequency signal with a particular area of the array, and as a result, the transform must be calculated over the entire array in order to determine locations of concentrations of signal energy of a particular spatial frequency. These disadvantages are further explained below.
The time to compute a one-dimensional transform of a linear array is proportional to the number of calculations, and for a linear array of n signal values may be represented by T(n) and a one-dimensional transform of n.sup.2 signal values represented by T(n.sup.2). On the other hand, the time required to compute the two-dimensional transform of n.sup.2 signal values in a square nxn array as a product of one-dimensional transforms would be at least 2nT(n) since there are n rows of data each of which requires a computational time of T(n) and n columns each of which also requires a computational time of T(n). Thus, where 2nT(n)&gt;T(n.sup.2), more time is required to perform a transform for an nxn array of data as a sequence of two one-dimensional transforms than to perform the same transform as a one dimensional transform of the same data reordered in a linear array.
For example, for the serial Fast Fourier Transform, T(n) in known to be proportional to nlogn so that T(n.sup.2) is proportional to n.sup.2 logn.sup.2 =2n(nlogn) and thus T(n.sup.2)=2n(T(n)) and therefore the use of a sequence of one-dimensional transforms to compute the transform of an nxn array should take no more time than reordering the array into a single linear array and performing a single one-dimensional transform. However for other transforms, and when transforms are computed in parallel, the disadvantages of computing a two-dimensional transform as a sequence of one-dimensional transforms can be very substantial. For example, parallel implementations of both the Fast Fourier Transform and the Haar transform require time T(n) proportional to log n to compute the transform of n signal values, from which it follows that T(n.sup.2)=2clog n whereas 2n(T(n))=2cnlog n, for some constant c. This shows that the ratio of time required to compute the transform of a two-dimensional signal array as a sequence of one-dimensional transforms to the time required to compute the transform by reordering the single values into a single linear array and performing a single one-dimensional transform, is proportional to n. The prior transforms of multi-dimensional signals such as two-dimensional images have been performed only by first computing a sequence of one-dimensional transforms.
As to the second disadvantage of computing multi-dimensional transforms by first calculating a sequence of one-dimensional transforms, the basis functions of most conventional one-dimensional transforms do not "localize" signal energy (associate a particular spatial frequency signal with a particular area of an array). For such transforms, which include the Fourier transform, the Sine transform, the Cosine transform, the Slant transform, the Hadamard transform, and the Walsh transform, signal energy is localized by calculating appropriate linear combinations of the transform basis functions. The failure of the individual basis functions of these transforms to localize signal energy is apparent from the fact that they have values that are different from zero in a neighborhood of each value of the independent variable, e.g. the spatial position variable x or y. For example, the basis functions of the Fourier transform, Sin(mKwx) and Cos(mKwx), where m=0,1,2, . . . ., w is the angular frequency variable, and K=constant, are not zero in the neighborhood of each value of x, and therefore do not localize signal energy.
There are one-dimensional transforms, such as the Haar transform and its generalizations, whose basis functions do localize signal energy. The Haar transform is generally well known and is described for example in IEEE Trans. Electromagn. Compat EMC-15:75-80 (1973); Diqital Image Processing, William K. Pratt, pages 254-256, John Wiley & Sons (1978); and Use of the Haar Transform and Some of its Properties in Character Recoqnition, Proc, 3rd Int'l. Conf. of Pattern Recognition, Pages 844-848, IEEE, New York, 1976.
The linear Haar transform of a mathematical function defined in a unit interval on a line is derived from the Haar matrix [h.sub.rs ], which is a 2.sup.P .times.2.sup.P matrix (P a positive integer) and whose elements h.sub.rs are given by the formula: EQU h.sub.0 s=1
for s contained in [0,1,2,...... 2.sup.P -1]; and EQU h.sub.rs =2.sup.m/2 for 2u/2.sup.m+1 .ltoreq.s/2.sup.P &lt;(2u+1)/2.sup.m+1 EQU h.sub.rs =-2.sup.m/2 for (2u+1)/2.sup.m+1 .ltoreq.s/2.sup.P &lt;(2u+2)/2.sup.m+1 (1) EQU h.sub.rs =0 elsewhere
for s contained in [0,1,2,...... 2.sup.P -1], r contained in [1,2,...... 2.sup.P -1], and where m is the greatest integer such that 2.sup.m is less than or equal to r and where u=r-2.sup.m.
For example, for P=3 and for r=3, the greatest integer m such that 2.sup.m is less than r is m=1 and therefore u=r-2.sup.m =3-2=1. Then substituting these values of m, u and r in formula (1) gives EQU h.sub.3s =2.sup.1/2 for 1/2.ltoreq.s/8&lt;3/4 EQU h.sub.3s =-2.sup.1/2 for 3/4.ltoreq.s/8&lt;1 EQU h.sub.3s =0 elsewhere
The respective Haar basis functions are the continuous linear representations of the Haar elements h.sub.rs as s varies from 0 to 2.sup.P -1. That is EQU h.sub.r (x)=h.sub.rs (s&lt;x&lt;s+1; all s contained in [0,1,2,...... 2.sup.P -1]). (1a)
These functions are illustrated in FIG. 1A for P=3. As can be seen from FIG. 1A and equation (1a), for the above example, h.sub.3 (x) is equal to 2.sup.1/2 for 4.ltoreq.x&lt;6, -2.sup.1/2 for 6.ltoreq.x&lt;8 and zero elsewhere. Therefore h.sub.3s is equal to 0 for s=0, 1, 2 and 3, is equal to 2.sup.1/2 for s=4 and 5, is equal to -2.sup.1/2 for s=6 and 7. Then the Haar function h.sub.3 (x) is equal to h.sub.3s (s.ltoreq.x&lt;s+1; all s contained in [0,1,2,...... 2.sup.P -1]).
Thus, FIG. 1A illustrates that the signal energy located along a line is represented by the coefficient of a single basis function corresponding to a segment of the line of appropriate size to accommodate the spatial frequency thereof and located at the appropriate spatial location.
However, multi-dimensional transforms which are computed as a sequence of one-dimensional transforms do not have this property. Thus, for example, even the basis functions of the two-dimensional Haar transform computed as a sequence of one-dimensional Haar transforms does not localize signal energy. This is because such transforms are product transforms in which the basis functions are products of one-dimensional basis functions. Even if the one-dimensional basis functions do localize energy, as in the case of the Haar basis functions, such localization is on many scales of localization. This means that high spatial frequency energy is localized on relatively small areas of an array while low spatial frequency energy is localized on relatively large areas of the array (that is, the scale of localization is inversely proportional to the spatial frequency). Therefore, the product basis functions are products ranging over all combinations of scales of localization of the one-dimensional basis functions and the transform coefficients thereof cannot individually define the degree of signal energy of a particular spatial frequency in a particular localized area of the signal array. As a consequence, the use of product transforms for the analysis of multi-dimensional signals does not provide an efficient means for isolating and measuring the energy of a signal by spatial frequency and location.
The product basis functions f.sub.ij (x,y)=h.sub.i (x)h.sub.j (y), i,j=0,1...2.sup.P -1, where h.sub.i (x) are the one-dimensional Haar transform basis functions defined above in formulae (1) and (1a) and h.sub.j (y) are the same functions with a different independent variable y for the two-dimensional Haar Transform, exhibit this characteristic and are illustrated for an 8.times.8 matrix (P=3 in the above formula (1)) in FIG. 1B. In FIG. 1B, the areas which are black and white are those where signal energy represented by the corresponding Haar coefficients is located, and as can be seen, energy at a location and of any particular scale of localization may be represented by the coefficients of more than one basis function. For example, energy localized in the bottom half of the matrix and of a scale equal to one half of the matrix may be represented in the coefficients of basis functions f.sub.20, f.sub.21, f.sub.02, f.sub.12, f.sub.03 and f.sub.13.